program Project1;

{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  arr = array of integer;
  arr2 = array [0..1] of integer;

var
  matrix: array of arr;
  list: array of arr2;
  vert: array of boolean;
  v, i, j, minv, current, sum, weight: integer;

begin
  read (v);
  setlength (matrix, v, v);
  setlength (vert, v);
  setlength (list, v-1);
  for i := 0 to v-1 do
    for j := 0 to v-1 do
      read (matrix[i, j]);
  sum:= 0;
  weight:= 0;
  current:= 0;
  vert[0]:= true;
  repeat
    minv:= current+1;
    for i := current+1 to v-1 do
      if ((matrix[current, minv]>matrix[current, i]) and (matrix[current, i]<>0) and (vert[i]=false)) then
        minv:= i;
    weight:= weight+matrix[current, minv];
    vert[minv]:= true;
    list[sum, 0]:= current;
    list[sum, 1]:= minv;
    current:= minv;
    inc(sum);
  until (sum=v);
  
  writeln (weight);
  for i := 0 to v - 2 do
    writeln (list[i, 0], ' ', list[i, 1]);
  write ('Write any number to close the program: ');
  read (sum);
end.
